class TreeNode():
    def __init__(self,val=0,left=None,right=None):
        self.val=val 
        self.left=left 
        self.right=right

from collections import deque
# def build_level(lst):
#     if len(lst)==0: return None
#     root=TreeNode(lst[0])
#     que=deque([root])
#     i=1 
#     while i<len(lst):
#         cur=que.popleft()
#         l=TreeNode(lst[i])
#         cur.left=l 
#         que.append(l)
#         if i+1<len(lst):
#             r=TreeNode(lst[i+1])
#             cur.right=r 
#             que.append(r)
#         i+=2 
#     return root

def build_level(lst):
    root=TreeNode(lst[0])
    que=deque([root])
    i,n=1,len(lst)
    while len(que)>0:
        cur=que.popleft()
        if i<n and lst[i]: #**
            cur.left=TreeNode(lst[i])
            que.append(cur.left)
        if i+1<n and lst[i+1]:
            cur.right=TreeNode(lst[i+1])
            que.append(cur.right)
        i+=2 
    return root 

def traversal_level(root):
    if not root: return
    ans=[]
    lst=[]
    que=deque([root])
    k,nextk=1,0
    while len(que)>0:
        cur=que.popleft()
        if cur: 
            lst.append(cur.val)
            if cur.left:
                que.append(cur.left)
                nextk+=1 
            if cur.right:
                que.append(cur.right)
                nextk+=1 
        #print('*',lst)
        if len(lst)==k:
            k,nextk=nextk,0 
            ans.append(lst)
            lst=[] #*

    return ans 
        

def traversal_level_2(root):
    if not root: return
    lst=[]
    que=deque([root])
    while len(que)>0:
        cur=que.popleft()
        if cur: 
            lst.append(cur.val)
            que.append(cur.left)
            que.append(cur.right)
        else: 
            lst.append(None)
    i=len(lst)-1
    while i>=0 and not lst[i]: i-=1
    return lst[:i+1]
        
root=build_level([3,9,20,None,None,15,7])
print(traversal_level(root))
print(traversal_level_2(root))


